package haxe.util;
import haxe.util.Compare;
import haxe.util.SortedCollection;
import haxe.util.Stack;
//import com.rozalski.log.Logger;

class ArrayHeap<T> extends SortedCollection<T>
{
	private var _a:Array<T>;
	public var size(getSize,null):Int;
	
	public function new( c:Comparator<T> )
	{
		super( c );
		_a = new Array();
	}
	
	public function add( o:T ):Void
	{
		super.add(o);
		var i:Int = _a.push( o ) - 1;
		var j:Int = (i-1)>>1;//parent
		var t:T;
		while( i > 0 && comp( _a[i], _a[j] ) < 0  )
		{
			t = _a[i];_a[i] = _a[j];_a[j] = t;//swap(i,j);
			i = (i-1)>>1;//gP(i);
			j = (i-1)>>1;//gP(i);
		}
	}
	
	public function extract( ):T
	{
		var r:T = _a.shift();
		if ( _a.length > 2 )
		{
			//restoring Heap property
			var o:T = _a.pop();
			_a.unshift(o);
			var i:Int = 0;
			var c:Int = ( i + 1 )<<1;
			var j = if ( comp( _a[(c-1)], _a[(c)] ) < 0 )c-1;else c;
			var t:T;
			while( i < _a.length-1 && comp( _a[i], _a[j] ) > 0 )
			{
				t = _a[i];_a[i] = _a[j];_a[j] = t;//swap
				i = j;
				c = ( i + 1 )<<1;
				j = if ( comp( _a[(c-1)], _a[(c)] ) < 0 )c-1; else c;//get minimal child
			}
		}
		else if ( _a.length == 2 && comp( _a[0], _a[1] ) > 0 )
		{
			var t:T;
			t = _a[0];_a[0] = _a[1];_a[1] = t;//swap
		}
		return r;
	}
	
	public function getFirst():T
	{
		return _a[0];
	}
	
	public function insert( o:T ):Void
	{
		add(o);
	}
	
	//todo - OPT !
	public function remove(o:T,?equals: T->T->Bool):Bool
	{
		if ( comp( o, _a[0] ) >= 0 && contains(o) )
		{
			var s:Stack<T> = new Stack();
			var i:T = extract();
			while(! eq( i, o ) )
			{
				s.push(i);
				i = extract();
			}
			while( !s.isEmpty() )
			{
				add( s.pop() );
			}
			return true;
		}else
			return false;
	}
	
	public function contains(o:T,?equals: T->T->Bool):Bool
	{
		if ( comp(o, _a[0] ) >= 0 )
		{
			for ( i in _a )
			{
				if ( eq( o, i ))
					return true;
			}
			return false;
		}else
			return false;
	}
	
	public function clear():Void
	{
		_a = new Array();
	}
	
	public function isEmpty():Bool
	{
		return _a.length == 0;
	}
	
	//WARNNING - not SORTED
	public function iterator():Iterator<T>
	{
		return _a.iterator();
	}
	
	public function toArray():Array<T>
	{
		return this._a.slice(0);
	}
	
	public function toString():String
	{
		return "ArrayHeap";
	}
	
	private function getSize():Int
	{
		return _a.length;
	}
	
	public static function main():Void
	{
		//Logger.setRedirection();
		var N:Int = 1000;
		var h:ArrayHeap<Int> = new ArrayHeap(null);
		var l:SortedLinkedList<Int> = new SortedLinkedList(null);
		var m:LinkedList<Int> = new LinkedList();
		var a:Array<Int> = new Array();
		var v:Array<Int> = new Array();
		var k:List<Int> = new List();
		
		var getTime:Dynamic = 
		#if flash
			flash.Lib.getTimer;
		#else neko
			neko.Sys.time;
		#else js
			null;
		#end
		
		for( i in 0...N )
			v.push( Math.round( Math.random()*N ) );
		
		var t:Int = getTime();
		for ( i in v )
		{
			h.add(i);
		}
		trace("ArrayHeap adding time : "+( getTime()-t));
		
		t = getTime();
		for ( i in v )
		{
			l.add(i);
		}
		trace("SortedLinkedList adding time : "+( getTime()-t));
		
		t = getTime();
		for ( i in v )
		{
			m.add(i);
		}
		trace("LinkedList adding time : "+( getTime()-t));
		
		t = getTime();
		for ( i in v )
			a.push(i);
		trace("Array pushing time : "+( getTime()-t));
		
		t = getTime();
		for ( i in v )
			k.add(i);
		trace("List adding time : "+(getTime()-t));
		
		////////////////////////////////////////
		//	Extracting
		///////////////////////////////////////
		
		t = getTime();
		while( !h.isEmpty() )
			h.extract();
		trace("ArrayHeap extracting time : "+(getTime()-t));
		
		t = getTime();
		while( !l.isEmpty() )
			l.removeFirst();
		trace("SortedLinkedList removing time : "+(getTime()-t));
		
		t = getTime();
		while( !m.isEmpty() )
			m.removeFirst();
		trace("LinkedList removing time : "+(getTime()-t));
		
		t = getTime();
		while( a.length != 0 )
			a.shift();
		trace("Array shifting time : "+(getTime()-t));
		
		t = getTime();
		while( ! k.isEmpty() )
			k.pop();
		trace("List poping time : "+(getTime()-t));
		
		////////////////////////////////////////
		//	Check sorting
		///////////////////////////////////////
		
		for ( i in v )
		{
			h.add(i);
			l.add(i);
			a.push(i);
		}
		
		var c:Comparator<Int> = IntComparator.getInstance();
		t = getTime();
		a.sort(c.compare);
		trace("Array first sorting time : "+(getTime()-t));
		
		a.push(Math.round( Math.random()*100) );
		
		t = getTime();
		a.sort(c.compare);
		trace("Array second sorting time : "+(getTime()-t));
		
		var i:Int = 0;
		var hv:Int;
		var lv:Int;
		var q:Queue<Int> = new Queue();
		while( !h.isEmpty())
		{
			q.enqueue(h.extract());
		}
		//trace(">"+q.toArray().join("|"));
		//trace(">"+l.toArray().join("|"));
		//trace(">"+a.join("|"));
		//trace("Heap|SortedLinkedList|Array");
	}
}